 /********************************************************************************************\
 * libeds - extensible data structures library                                                *
 * Copyright (C) 2006, Dan Kruchinin, <just.asgard@gmail.com>                                 *
 *                                                                                            *
 * -> trees/bin_tree.c                                                                        *
 * Common functionality for all binary trees. It can be used by developer or not,             *
 * developer is god, [he/she] makes choice ;).                                                *
 * So, implementation of binary tree any kind is flexible and here you can                    *
 * see only poor basis.                                                                       *
 *                                                                                            *
 * This library is free software; you can redistribute it and/or modify it under the terms of *
 * the GNU Lesser General Public License as published by the Free Software Foundation;        *
 * either version 2.1 of the License, or (at your option) any later version.                  *
 *                                                                                            *
 * This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;  *
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  *
 * See the GNU Lesser General Public License for more details.                                *
 *                                                                                            *
 * You should have received a copy of the GNU Lesser General Public License along with this   *
 * library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,  *
 * Boston, MA 02111-1307 USA                                                                  *
 \********************************************************************************************/

#include <stdio.h> /* FIXME: remove after debugging */
#include <stdlib.h>
#include "ds.h"
#include "safe_alloc.h"
#include "errors.h"
#include "trees/bin_tree.h"

#define BIT_NERRS          3 /* number of errors */
#define DSERR_BIT_NINSERT -1 /* insert function is not present */
#define DSERR_BIT_NDELETE -2 /* delete function is not present */
#define DSERR_BIT_NFIND   -3 /* find function is not present */

DS_ERRNO_POSITION(__bit_errpos);
static char* __bit_errs[BIT_NERRS] = {
  "'insert' function is not present.",       /* DSERR_BIT_NINSERT */
  "'delete' function is not present. ",      /* DSERR_BIT_NDELETE */
  "'find' function is not present.",         /* DSERR_BIT_NFIND */
};

void _bit_init_main(void)
{
  if(!_ds_pos_is_reg(__bit_errpos))
	__bit_errpos = _ds_reg_errno_pos(__bit_errs, BIT_NERRS);
}

/* this function should be used for binary tree allocation */
struct _bit* _bit_allocate(void)
{
  struct _bit* bt;

  bt = (struct _bit*)scalloc(1, sizeof(*bt));
  return bt;
}

/* and this function should be used for binary tree destroyment */
void _bit_destroy(struct _bit* tree)
{
  sfree(tree);
}

/* create new binary tree node */
bit_node* _bit_node_new(void)
{
  bit_node* n;
  
  n = (bit_node*)scalloc(1, sizeof(*n));
  return n;
}

/* destroy binary tree node */
void _bit_node_destroy(bit_node* n)
{
  sfree(n);
}

/* simple left rotation */
bit_node* _bit_rotate_left(struct _bit* tree, bit_node* n)
{
  bit_node* parent;

  if(node_empty(n->right))
    return NULL;

  parent = n->right;
  n->right = parent->left;
  parent->left = n;
  parent->parent = n->parent;
  _bit_recount_nodes(n); /* take care about subnodes number */

  if(!node_empty(n->right))
    n->right->parent = n;
  if(!node_empty(n->parent)) {
    if(parent->parent->left == n)
      parent->parent->left = parent;
    else
      parent->parent->right = parent;

  }

  n->parent = parent;

  /* rewrite root pointer if really need */
  if(tree->root == n)
    tree->root = parent;

  /* take care about subnodes number one more time... */
  _bit_recount_nodes(parent);
  return n->parent;
}

/* simple right rotation(factically, the sane as previuos algorithm, but change left to right and vice versa) */
bit_node* _bit_rotate_right(struct _bit* tree, bit_node* n)
{
  bit_node* parent;

  if(node_empty(n->left))
    return NULL;
  
  parent = n->left;
  n->left = parent->right;
  parent->right = n;
  parent->parent = n->parent;
  _bit_recount_nodes(n);

  if(!node_empty(n->left))
    n->left->parent = n;
  if(!node_empty(n->parent)) {
    if(parent->parent->left == n)
      parent->parent->left = parent;
    else
      parent->parent->right = parent;
  }

  n->parent = parent;

  if(tree->root == n)
	tree->root = parent;
 
  _bit_recount_nodes(parent);
  return n->parent;
}

int _bit_insert(struct _bit* t, void* k, void* v)
{
  _ds_set_errno(DSERR_BIT_NINSERT, __bit_errpos);
  return DSERR_BIT_NINSERT;
}

int _bit_delete(struct _bit* t, bit_node* n)
{
  _ds_set_errno(DSERR_BIT_NDELETE, __bit_errpos);
  return DSERR_BIT_NDELETE;
}

bit_node* _bit_find(struct _bit* t, const void* k)
{
  _ds_set_errno(DSERR_BIT_NFIND, __bit_errpos);
  return BIT_SEARCH_ERR;
}

/* return left subnode */
bit_node* _bit_node_left(const bit_node* n)
{
  if(node_empty(n))
    return NULL;

  return n->left;
}

/* return right subnode */
bit_node* _bit_node_right(const bit_node* n)
{
  if(node_empty(n))
    return NULL;

  return n->right;
}

/* return node parent */
bit_node* _bit_node_parent(const bit_node* n)
{
  if(node_empty(n))
    return NULL;

  return n->parent;
}

/* return tree root */
bit_node* _bit_root(const struct _bit* tree)
{
  return tree->root;
}

/* return node brother */
bit_node* _bit_node_brother(const bit_node* n)
{
  if(node_empty(n))
    return NULL;
  if(node_empty(n->parent))
    return NULL;
  if(n->parent->left == n)
    return n->parent->left;

  return n->parent->right;
}

/* return node, that goes after current node in sorted tree structure */
bit_node* _bit_node_successor(bit_node* n)
{
  bit_node *tmp, *parent;

  /* if right subtree is not empty, node successor is most left node in right subtree */
  if(!node_empty(n->right)) {
    tmp = n->right;

    while(!node_empty(tmp->left))
      tmp = tmp->left;

    return tmp;
  }

  /* otherwise, node successor is highes node parent if node is in right parent subtree */
  tmp = n;
  parent = tmp->parent;

  while(!node_empty(parent) && (tmp == parent->right)) {
    tmp = parent;
    parent = parent->parent;
  }

  return parent;
}

/* return node, that goes berfore current node in sorted tree structure */
bit_node* _bit_node_predecessor(bit_node* n)
{
  bit_node *tmp, *parent;

  /* if left subtree is not empty, node predecessor is most right node in left subtree */
  if(!node_empty(n->left)) {
    tmp = n->left;

    while(!node_empty(tmp->right))
      tmp = tmp->right;

    return tmp;
  }

  /* otherwise, node predecessor is highest parent, if node is in left parent subtree */
  tmp = n;
  parent = tmp->parent;

  while(!node_empty(parent) && (tmp == parent->left)) {
    tmp = parent;
    parent = parent->parent;
  }

  return parent;
}

/* recount subnodes number in node */
void _bit_recount_nodes(bit_node* node)
{
  if(node_empty(node))
    return;
  
  node->_nofnodes = 0;
  
  if(!node_empty(node->left))
    node->_nofnodes += node->left->_nofnodes + 1;
  if(!node_empty(node->right))
    node->_nofnodes += node->right->_nofnodes + 1;
}

/* tree height is a biggest tree level. */
int _bit_node_height(bit_node* n)
{
  int lh, rh;

  if(node_empty(n))
	return 0;

  lh = rh = 0;
  
  lh = _bit_node_height(n->left);
  rh = _bit_node_height(n->right);

  if(lh >= rh)
    return (lh + 1);

  return (rh + 1);
}

/*
 *
 * return tree internal path len(summary count of all internal tree nodes)
 * - internal node is a node, wich has not left and right subnodes
 */
int _bit_node_ipl(bit_node* n)
{
  int ipl = 0;

  if(node_empty(n))
	return 0;

  ipl += _bit_node_ipl(n->left);
  ipl += _bit_node_ipl(n->right);

  if(node_empty(n->left) && node_empty(n->right))
    ipl++;

  return ipl;
}

/*
 *
 * return tree external path len(summary count of all external tree nodes)
 * - external node is a node, wich has both left and right subnodes
 */
int _bit_node_epl(bit_node* n)
{
  int epl = 0;

  if(node_empty(n))
	return 0;
	
  epl += _bit_node_epl(n->left);
  epl += _bit_node_epl(n->right);

  if(!node_empty(n->left) && !node_empty(n->right))
    epl++;

  return epl;
}

/* return node subnodes number */
int _bit_node_subnodes(const bit_node* n)
{
  if(node_empty(n)) {
    _ds_set_errno(DSERR_EMPTY_NODE, DS_ERRPOS_MAIN);
    return DSERR_EMPTY_NODE;
  }

  return n->_nofnodes;
}


